package a309.最佳买卖股票时机含冷冻期;

/**
 * 动态规划：定义状态-》状态转移
 * 第i天结束后有三种状态,f[i][j]记作第i天结束后累计最大的收益
 *      持有股票（当天买入或之前买入） f[i][0]
 *      不持有股票且处于冷冻期(当天卖出) f[i][1]
 *      不持有股票且不处于冷冻期（之前卖出） f[i][2]
 * 状态转移：
 *      若当天结束后持有股票，假设之前买入股票，f[i][0]=f[i-1][0]；
 *          假设当天买入股票，那么前一天结束后不处于冷冻期，由于是是负收益，f[i][0]=f[i][2]-prices[i]
 *          因此 f[i][0]=Math.max(f[i-1][0],f[i][2]-prices[i])]
 *      若当天结束后不持有股票且处于冷冻期，说明当天刚卖了股票，那么前一天一定持有股票
 *          因此f[i][1]=f[i-1][0]+prices[i]
 *      若当天结束后不持有股票且不处于冷冻期，说明之前卖了
 *          因此f[i][2]=Math.max(f[i-1][1],f[i-1][2])
 *
 *   最终结果Math.max(f[n][1],f[n][2]),注意最后一天持有股票没有意义（卖出还能增加点收益）
 *
 */
class Solution {
    public int maxProfit(int[] prices) {
        int n=prices.length;
        int[][] f=new int[n][3];
        // 初始化
        f[0][0]=-prices[0]; // 只能当天买入
        for (int i = 1; i <n; i++) {
            //  之前买入或当天买入
            f[i][0]=Math.max(f[i-1][0],f[i-1][2]-prices[i]);
            f[i][1]=f[i-1][0]+prices[i];
            f[i][2]=Math.max(f[i-1][1],f[i-1][2]);
        }
        return Math.max(f[n-1][1],f[n-1][2]);
    }
}